1. Field of the Invention
The present invention relates to deployment of interior gateway routing protocols in networks having movable network nodes, for example a mobile ad hoc network (MANET) routing protocol.
2. Description of the Related Art
Wide area packet switched networks such as the Internet have become an integral part of worldwide commerce in part due to the ability of different networks to interoperate without central control. In particular, the decentralization of control is possible due to routing protocols which enable routers to communicate amongst each other and share routing information: routing protocols include operations such as router advertisement, router discovery or neighbor discovery, link state advertisement, and the sharing of all or at least a portion of respective routing tables:
Numerous interior gateway routing protocols (IGPs) have been developed to satisfy various design requirements, including optimality (selecting the optimal route), simplicity and low overhead to minimize burden on system resources, robustness (i.e., maintaining operability despite failures within the network), rapid convergence, stability, and flexibility in adapting to network changes. Such routing protocols can be either proactive or reactive: proactive routing protocols determine a path to a destination before the path is needed to forward a packet, whereas reactive routing protocols determine the path to a destination in response to a need to forward a packet to the destination.
The overall sequence of operations of interior gateway routing protocols (e.g., distance vector, link state) in building a loop-free path can be summarized with respect to FIG. 1. Such routing protocols in general begin with neighbor discovery in step 10 during initialization of the network, where a router discovers other routers that are within a prescribed interior of an administrative domain: the administrative domain determines the boundary of the network as an Autonomous System. The example of FIG. 1 assumes a fixed network, where network nodes (e.g., routers, hosts, etc.) are “fixed” at respective locations relative to each other, unlike mobile nodes which inherently move relative to each other (described in further detail below).
The fixed router in the fixed network then stores a candidate set of neighboring routers (“neighbors”) within the administrative domain (i.e., “interior neighbors”), and performs in step 12 some form of a database exchange with the candidate set of neighbors, enabling the router and neighboring routers each to calculate in step 14 an acyclic graph for each identifiable destination in the administrative domain. The acyclic graph is calculated in step 14 according to a loop-free network topology, and according to prescribed optimization parameters and metrics for the corresponding routing protocol, for example lowest latency, least cost, shortest hops, etc. The acyclic graphs calculated in step 14 are used to build a forwarding table for each destination in step 16, enabling the router to begin forwarding packets in step 18.
Once the fixed router has established the forwarding table in step 16 in order to forward packets in step 18, the router performs neighbor management in steps 20 and 22. In particular, the router starts a timer (a “stale timer”) (T) in step 20 to monitor the state of the neighbors in the candidate set of neighbors: the routing protocol is configured to wait in step 22 for a prescribed time interval (T=T1) to determine if a given neighbor is detected within the prescribed time interval (T1).
If in step 22 the neighbor is not detected within the prescribed time interval (T=T1), the router declares the neighbor as stale for purposes of its internal forwarding table; if in step 22 the neighbor is not detected within a further prescribed time interval (T=T2, where T2>T1), the router removes the stale neighbor from the candidate set of neighbors in step 22, and performs a new database exchange according to the routing protocol to inform the neighbors in step 12 that the stale neighbor is no longer reachable. The process repeats in recalculating acyclic graphs in step 14, and building the forwarding tables in step 16.
A fundamental aspect of the timer (T) in step 20 is that the network is assumed to be stable (i.e., the network has converged and routes have been optimized) for a prescribed time interval (T=T0, where T0<T1) after having started the timer (T). Convergence is the process of agreement, by all routers, on optimal routes; in other words, convergence refers to the initial calculation or recalculation of routes by a router and the distribution of routing information to the other routers, as illustrated in steps 12 and 14, in order to maintain consistency between the routers in view of the recalculation of routes. The assumed stability in the network during the prescribed time interval (T=T0), also referred to as the “stability interval”, provides a minimum time interval during which acyclic graphs and forwarding tables do not need to be recalculated. The prescribed stability interval (T=T0) is manually configured by a traffic engineer to balance between the amount of network traffic that is consumed by the database exchange process and the amount of processor time consumed by the router in recalculation of acyclic graphs and forwarding tables (i.e., minimizing network and router resources for neighbor maintenance and route maintenance), versus the accuracy of the router in identifying the topology of the network (i.e., minimizing the staleness of the network information).
In addition, the prescribed stability interval (T=T0) is manually configured by the traffic engineer based on the assumption that the loss of a neighbor in the fixed network is due to physical interruptions in the network, for example a hardware or software failure in a neighboring node, a link failure, scheduled maintenance of a node or link, etc; as such the traffic engineer assumes a relatively low probability of failure. Hence, the routing protocol executed by the routers in the network is configured by a traffic engineer for operating in a fixed network having a low probability of failures; in the event of a failure that result in the loss of an existing path, however, an interior gateway routing protocol as described above enables an alternate path to a destination to be determined due to the loss of the existing path.
Optimized selection of the stability interval (T=T0) can be important in minimizing “route flapping”, where paths to a given destination are changed repeatedly due to intermittent errors. Hence, traffic engineering requires consideration of parameters and attributes such as topology, bandwidth, traffic, throughput requirements, etc.
The foregoing considerations by traffic engineers in determining an appropriate stability interval are further complicated in a mobile network, where nodes are no longer fixed but are mobile as described in the Internet Engineering Task Force (IETF) Request for Comments (RFC) 3775 and RFC 3963. In the case of a mobile network, all of the previously static network attributes can now change over time, including the identity of neighboring nodes, the availability of links, the shape of the network topology, etc.
Hence, the traffic engineering described above with respect to fixed networks is less relevant in mobile networks, because the underlying assumptions of a fixed network no longer apply; consequently, the prescribed stability interval (T=T0) is substantially less relevant in a mobile network because the continual variations in neighbor identity, link availability, network topology, etc., prevent the mobile network from ever being “stable” as defined in fixed networks.
In other words, the issue confronting traffic engineers has been addressed from the perspective of how to determine the minimum length of time (Tm) to wait before assuming that a neighboring node has disappeared (i.e., is no longer available) in order to trigger reconvergence of the routing protocol. As described above, this issue historically has been addressed in fixed networks by setting a prescribed stability interval (Tm=T0) for fixed nodes assumed to have a relatively high degree of reliability (i.e., a relatively low probability of unavailability).
Attempts to apply existing routing protocols to a mobile ad hoc network do not adequately address the fundamental issue of mobility of network nodes. For example, the Fisheye routing protocol, as described in the publication by Pei et al, “Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Networks”, suggests reducing the frequency of link state update messages as the number of hops to an affected router increases. Hence, Pei et al. suggests that link state updates related to closer nodes are distributed to next hop nodes more frequently than link state updates related to further nodes; in other words, the quality of the topological information of an identified node in a topology table of a given node is inversely proportional to the hop count distance between the given node and the identified node.
Although the above-described Fisheye routing protocol may reduce route recalculation and flooding of link state advertisement messages due to changes in distant network nodes, it does not address the fundamental issue of mobility of network nodes, as illustrated with respect to FIG. 2.
FIG. 2 is a diagram illustrating a mobile ad hoc network 30 formed initially between mobile routers 32a and 32b via a wireless link 34 before a time reference “t0−2” (i.e., before detecting the presence of the mobile router 32c located at its position “Ct0−2”). The mobile routers 32a, 32b and 32c may be deployed, for example, on respective jet fighter planes. As illustrated in FIG. 2, the mobile routers 32a and 32b are moving at respective velocity vectors VA and VB that are substantially equal to each other (VA=VB); hence, the relative velocity (VR) between the mobile routers 32a and 32b is negligible (VRAB=VRBA=0), enabling the mobile routers 32a and 32b to establish a reliable wireless communication link between each other, and establish forwarding tables as described above with respect to FIG. 1. The mobile router 32c, however, is not detected by the mobile routers 32a or 32b while the mobile router 32c is at its position “Ct0−2” at time “t0−2”, as illustrated by the absence of any wireless links 34 and the dashed lines at the position “Ct0−2”.
The jet fighter plane carrying the mobile router 32c is moving at the corresponding velocity vector VC, where the velocity vector VC is the same magnitude but opposite direction of the velocity vectors VA and VB (VC=−VA). Hence, if the magnitude (i.e., speed) of each velocity vector VA, VB, and VC is mach 1 (approximately 1,225 km/h or 761 miles/hr), the relative speed velocity between the mobile router 32c and the mobile routers 32a and 32b would be mach 2 (VRAC=VRBC=2VA=mach 2).
As illustrated in FIG. 2, the mobile routers 32a and 32b detect the mobile router 32c (and mobile router 32c detects mobile routers 32a and 32b) as the mobile router 32c moves to its corresponding position “Ct0−1” at time reference “t0−1”, as illustrated by the establishment of the wireless links 34a and 34b. Each of the mobile routers 32a, 32b, and 32c respond to the detection of the mobile router 32c and establishment of the links 34a, 34b by performing database exchange, recalculating acyclic graphs and building forwarding tables as described above with respect to FIG. 1, during which time the mobile router 32c has moved to the position “Ct0” at time reference “t0”. By the time the mobile routers 32a, 32b and 32c can begin to forward packets to each other as described with respect to step 18 of FIG. 1, the mobile router 32c will have moved to the position “Ct0+1” at time reference “t0+1”. Consequently, the continued movement of the mobile router 32c to the position “Ct0+2” at time reference “t0+2” will cause the mobile routers 32a and 32b to lose connectivity with the mobile router 32c, requiring the mobile routers 32a and 32b to perform route recalculation in view of the loss of the mobile router 32c. 
Hence, the mobile router 32c belongs to the mobile ad hoc network of FIG. 2 only for the time interval (TC) between “t0−1” and “t0+1”, referred to herein as the “connected time interval” (TC=(t0+1)−(t0−1)=2 time units). This connected time interval is inversely proportional to the relative velocity between the mobile routers (VR=2VA=2VB); therefore, while at slower speeds (e.g., VR<200 mph) the connected time interval may be adequate for the mobile ad hoc routers 32a, 32b, and 32c to recalculate the network and perform network convergence and meaningful data exchange (e.g., data synchronization by application layer processes), at higher speeds (e.g., VR>1500 mph) the connected time interval (TC) may be so brief (e.g., TC=2 microseconds) that no meaningful data exchange can take place, such that the route recalculation and database exchange by mobile routers 32a and 32b to add mobile router 32c provides no beneficial effect.
Further, failure to complete network convergence within the connected time interval may result in network disruption while the mobile routers 32a and 32b need to recalculate the original routes upon the loss of the mobile router 32c at time “t0+2”. Hence, the route recalculation by the mobile routers 32a and 32b in response to detecting the mobile router 32c may result in a disruption of the optimized MANET having initially been established between the mobile routers 32a and 32b. 
As apparent from the foregoing description of FIG. 2, the proximity of a node as relied on in the Fisheye routing protocol has no relevance to the stability of a dynamic network with respect to determining whether to distribute routing information: even though the mobile router 32c is one hop away from the mobile routers 32a and 32b, the addition of the mobile router 32c does not necessarily benefit the routers 32a and 32b, and may in fact disrupt the existing MANET network 30.
Other proposals in the art, such as Carofiglio et al., “Analysis of Route Stability in MANETs”, suggest estimating a path duration based on probability characteristics, but does not address the effect of path duration in determining whether to perform route recalculation.
Another proposal described in Bush et al., “The Limits of Motion Prediction Support for Ad hoc Wireless Network Performance”, suggests exchanging “models of motion” and using these models to determine “the frequency at which routing updates are required.” In particular, Bush et al. assumes that a node will know the relative motion of other nodes, and that a node will be able to determine how often to exchange routing information with other nodes. However, Bush et al. does not describe how a node learns of the relative motion of another node. In other words, node A only knows about the actual motion of A, but does not know about the actual motion of node B; consequently, each node independently determines the frequency of outputting its own routing updates based on its own corresponding motion (i.e., relative motion of nodes). Hence, Bush et al. does not address the problem of how to determine the relative motion of other nodes without exchanging information between the nodes.
A solution to these and other problems is described in the accompanying brief description of the attached drawings and the accompanying description of embodiment(s) of the invention as specified in the appended claims, the description of the embodiment(s) including at least one best mode for carrying out the invention.